﻿#include "stdafx.h"
#include "SearchSortedListsPos.h"

using namespace std;

namespace algorithm {
vector<int> CSearchSortedListsPos::Search(vector<int>& nums, int target)
{
    int size = (int)nums.size();
    if (size <= 0) {
        return initializer_list<int>{ -1,-1 };
    }
    else if (size == 1) {
        return target == nums[0] ? initializer_list<int>{0, 0} : initializer_list<int>{-1,-1};
    }
    // 二分法寻找列表中是否包含目标值
    int idx = BinarySearch(nums, 0, size, target);
    if (idx == -1) {
        // 不包含则直接返回
        return initializer_list<int>{ -1,-1 };
    }
    // 从寻找到的目标值索引开始向左找到相同的值
    int left = idx;
    while (1) {
        int find = BinarySearch(nums, 0, left, target);
        if (find == -1) {
            break;
        }
        left = find;
    }
    for (int i = left - 1; i >= 0; i--) {
        if (nums[i] == target) {
            left = i;
        }
    }
    // 从寻找到的目标值索引开始向右找到相同的值
    int right = idx;
    while (1) {
        int find = BinarySearch(nums, right + 1, size, target);
        if (find == -1) {
            break;
        }
        right = find;
    }
    return initializer_list<int>{ left, right };
}

int CSearchSortedListsPos::BinarySearch(std::vector<int>& nums, int left, int right, int target)
{
    int idx = -1;
    while (left<right) {
        if (right - left <= 1) {
            if (nums[left] == target) {
                idx = left;
            }
            break;
        }
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target) {
            idx = mid;
            break;
        }
        else if(nums[mid]<target){
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }
    return idx;
}
}
